'''
1. 深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。
   其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
2. 当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。
   整个进程反复进行直到所有节点都被访问为止。
3. 对于同一颗的树或图，其DFS序不一定唯一。
4. 深度优先搜索使用栈（stack）来实现，栈(stack)有着先进后出的特性。
————————————————
原文链接：https://blog.csdn.net/weixin_45758642/article/details/122945316

使用场景：
1.  BFS是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为BFS搜索过程中遇到的解一定是离根最近的，
    所以遇到一个解，一定就是最优解，此时搜索算法可以终止。这个时候不适宜使用DFS，因为DFS搜索到的解不一定是离根最近的，
    只有全局搜索完毕，才能从所有解中找出离根的最近的解。（当然这个DFS的不足，可以使用迭代加深搜索ID-DFS去弥补）。

2.  空间优劣上，DFS是有优势的，DFS不需要保存搜索过程中的状态，而BFS在搜索过程中需要保存搜索过的状态，
    而且一般情况需要一个队列来记录。

3.  DFS适合搜索全部的解，因为要搜索全部的解，那么BFS搜索过程中，遇到离根最近的解，并没有什么用，也必须遍历完整棵搜索树，
    DFS搜索也会搜索全部，但是相比DFS不用记录过多信息，所以搜素全部解的问题，DFS显然更加合适。
'''
from typing import List

# 创建树节点类val：值，left：左子树，right：右子树
class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None


# 深搜遍历二叉树
def DFS(root: TreeNode) -> List[int]:
    '''
    输出结果从左到右
    '''
    # 创建存放结果数组
    if not root: return []
    res = []
    # 创建栈，栈具有后进先出的特性，首先放入根节点
    stack = [root]
    # 循环栈
    while stack:
        # 取出栈最后一个元素
        currentNode = stack.pop()
        # 田间取出元素的值
        res.append(currentNode.val)
        '''先放右树成员进栈，再让左树进栈，以达到输出结果先左后右'''
        # 是否含右子树
        if currentNode.right:
            # 添加右子树到栈
            stack.append(currentNode.right)
        # 是否含左子树
        if currentNode.left:
            # 添加左子树到栈
            stack.append(currentNode.left)

    # 返回结果
    return res


if __name__ == "__main__":
    tree = TreeNode(4)  # 添加根节点
    tree.left = TreeNode(9)  # 添加根左子树
    tree.right = TreeNode(0)  # 添加根右子树，以下以此类推
    tree.left.left = TreeNode(5)
    tree.left.right = TreeNode(1)
    tree.right.left = TreeNode(3)
    tree.right.right = TreeNode(2)
    tree.left.left.left = TreeNode(10)
    tree.right.left.right = TreeNode(7)

    print(DFS(tree))
    # [4, 9, 5, 10, 1, 0, 3, 7, 2]













